package justtry.sort;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by weishaofei on 2017/12/11.
 */
public class HeapSort extends Sort {

    @Override
    public void sort(List<Integer> list) {
        int length = list.size() - 1;
        System.out.println(length);
        for (int i = length / 2; i >= 1; i--) {
            sink(list, i, length);
            System.out.println(list);
        }
        System.out.println("构造完成" + list);
        while (length>1) {
            exchange(list, 1, length);
            System.out.println(list);
            sink(list, 1, --length);
        }
        System.out.println(list);
    }

    private void sink(List<Integer> list, int target, int length) {
        while (target * 2 <= length) {
            int j = target * 2;
            if (j < length && less(list, j, j + 1)) {
                j = j + 1;
            }
            if (less(list, j, target)) {
                break;
            }
            exchange(list, target, j);
            target = j;
        }
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<Integer>();
        list.add(-1);
        list.add(23);
        list.add(83);
        list.add(13);
        list.add(53);
        list.add(63);
        list.add(73);
        list.add(43);
        list.add(99);
        list.add(89);

        new HeapSort().sort(list);
    }
}
